package lc2;

import java.util.*;

import org.junit.Test;

import util.BracketUtils;

public class Ex253 {
    class Solution {//利用优先队列来存储右端点，就可以不遗漏之前的右端点
        public int minMeetingRooms(int[][] arr) {
            Arrays.sort(arr, (n1, n2) -> {
                // [[0, 30],[5, 10],[15, 20]]
                //[[0, 30],[15, 20],[5, 10]]
                return n1[0] - n2[0];
                /**
                 * 若不按照开始时间排序，开始时间可能增长过快，导致原本不用在增加会议室的场合增加了会议室
                 */
            });
            Queue<Integer> queue = new PriorityQueue<>();
            queue.offer(arr[0][1]);
            for (int i = 1; i < arr.length; i++) {
                int top = queue.peek();
                if (top <= arr[i][0]) {
                    queue.poll();
                }
                queue.offer(arr[i][1]);
            }
            return queue.size(); //之前踩在脚下的已经被替换掉了
        }
    }
    class Solution1 {//思路对，做法有问题:我会粗暴的取last和cur的最小右端点，而之前的右端点被抹除了，可能之前的右端更优
        public int minMeetingRooms(int[][] arr) {
            int cnt = 1;
            Arrays.sort(arr, (n1, n2) -> {
                return n1[0] != n2[0] ? n1[0] - n2[0] : n1[1] - n2[1];
            });
            Deque<int[]> deque = new ArrayDeque<>();
            int[] last;
            for (int i = 0; i < arr.length; i++) {
                if (!deque.isEmpty()) {
                    last = deque.peek();
                    if (last[1] > arr[i][0]) { //存在冲突
                        cnt++;
                        if (last[1] > arr[i][1]) {
                            last[0] = arr[i][0];
                            last[1] = arr[i][1]; //贪心，最小时间跨度
                        }
                    } else if (last[1] == arr[i][0]) {
                        //可以共用
                        last[1] = arr[i][1];
                    } else {
                        //可以共用
                        deque.offer(arr[i]);
                    }
                } else {
                    deque.offer(arr[i]);
                }
            }

            return cnt;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray( "[[0, 30],[15, 20]],[5, 10]");
        System.out.println(s.minMeetingRooms(nums));
    }
}
